/*
题目: N皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
https://leetcode.cn/problems/n-queens/
 */
public class SolveNQueens {
    List<List<String>> res = new ArrayList<> ();
    int n = 0;

    public List<List<String>> solveNQueens(int n) {
        char[][] grid = new char[n][n]; //二维数组, 表示棋盘
        this.n = n;
        initArray(grid);
        backTrack(grid, 0);
        return res;
    }

    private void backTrack(char[][] grid, int depth) {
        if (depth >= n) {
            res.add(parseToString(grid));
            return ;
        }

        for (int i = 0; i < n; i++) {
            grid[depth][i] = 'Q'; //放置皇后
            if (check(grid, depth, i) == false) {
                grid[depth][i] = '.';
                continue ;
            }
            backTrack(grid, depth + 1);

            grid[depth][i] = '.';
        }
    }

    //判断这个棋盘皇后是否合法
    private boolean check(char[][] grid, int x, int y) {
        //求行
        for (int i = 0; i < n; i++) {
            if (i == x) {
                continue;
            }
            if (grid[i][y] == 'Q') {
                return false;
            }
        }

        //求列
        for (int i = 0; i < n; i++) {
            if (i == y) {
                continue;
            }
            if (grid[x][i] == 'Q') {
                return false;
            }
        }

        //斜
        int a = x - 1;
        int b = y - 1;
        while (a >= 0 && b >= 0) {
            if (grid[a][b] == 'Q') {
                return false;
            }
            a--;
            b--;
        }

        a = x - 1;
        b = y + 1;
        while (a >= 0 && b < n) {
            if (grid[a][b] == 'Q') {
                return false;
            }
            a--;
            b++;
        }

        a = x + 1;
        b = y - 1;
        while (a < n && b >= 0) {
            if (grid[a][b] == 'Q') {
                return false;
            }
            a++;
            b--;
        }

        a = x + 1;
        b = x + 1;
        while (a < n && b < n) {
            if (grid[a][b] == 'Q') {
                return false;
            }
            a++;
            b++;
        }

        return true;
    }

    private List<String> parseToString(char[][] grid) {
        List<String> ret = new ArrayList<> ();
        for(int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(grid[i][j]);
            }
            ret.add(sb.toString());
        }
        return ret;
    }

    private void initArray(char[][] grid) {
        for (int i = 0; i < n; i++) {
            Arrays.fill(grid[i], '.');
        }
    }
}